{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Pivot Integer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pivotInteger"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出中枢整数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数 <code>n</code> ，找出满足下述条件的<strong> 中枢整数</strong> <code>x</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1</code> 和 <code>x</code> 之间的所有元素之和等于 <code>x</code> 和 <code>n</code> 之间所有元素之和。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回中枢整数<em> </em><code>x</code> 。如果不存在中枢整数，则返回 <code>-1</code> 。题目保证对于给定的输入，至多存在一个中枢整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 8\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6 是中枢整数，因为 1 + 2 + 3 + 4 + 5 + 6 = 6 + 7 + 8 = 21 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>1 是中枢整数，因为 1 = 1 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>可以证明不存在满足题目要求的整数。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-pivot-integer](https://leetcode.cn/problems/find-the-pivot-integer/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-pivot-integer](https://leetcode.cn/problems/find-the-pivot-integer/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['8', '1', '4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        i = 1\n",
    "        j = n + 1\n",
    "        while i < j:\n",
    "            k = (i + j) >> 1\n",
    "            a = (1 + k) * k >> 1\n",
    "            b = (k + n) * (n - k + 1) >> 1\n",
    "            if a < b:\n",
    "                i = k + 1\n",
    "            else:\n",
    "                j = k\n",
    "        return i if (1 + i) * i == (i + n) * (n - i + 1)  else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        for i in range(1, n+1):\n",
    "            if sum(x for x in range(1, i+1)) == sum(y for y in range(i, n+1)):\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        arr = []\n",
    "        for i in range(1, n + 1):\n",
    "            arr.append(i)\n",
    "        ret = -1\n",
    "        for i in range(1, n + 1):\n",
    "            if (sum(arr[:i]) == sum(arr[i - 1: n + 1])):\n",
    "                ret = arr[i - 1]\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        def cal(n,x):\n",
    "            left = x*(x-1)//2\n",
    "            right = (n+x+1)*(n-x)//2\n",
    "            return left<right\n",
    "        l, r = 1, n\n",
    "        while l<r:\n",
    "            x = (l+r)//2\n",
    "            if cal(n,x):\n",
    "                l = x+1\n",
    "            else:\n",
    "                r = x\n",
    "        if l*(l-1)//2==(n+l+1)*(n-l)//2:\n",
    "            return l\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        sums = [0]\n",
    "        for i in range(1,n+1):\n",
    "            sums.append(sums[-1] + i)\n",
    "        print(sums)\n",
    "        for i in range(1, n+1):\n",
    "            if (sums[-1] - sums[i-1]) == (sums[i]):\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        from itertools import accumulate\n",
    "        arr=list(accumulate(list(range(1,n+1))))\n",
    "        print(arr)\n",
    "        for i in range(n):\n",
    "            if arr[i]==arr[-1]-arr[i]+i+1:\n",
    "                return i+1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        temp = (1 + n) * n // 2\n",
    "        total = 0\n",
    "        for i in range(1, n + 1):\n",
    "            total += i\n",
    "            if total * 2 == temp + i:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        all_sum = sum([i for i in range(1, n+1)])\n",
    "        left_sum = 0\n",
    "        for i in range(1, n+1):\n",
    "            half_sum = all_sum - i\n",
    "            if half_sum % 2 != 0:\n",
    "                left_sum += i\n",
    "                continue\n",
    "            elif left_sum == half_sum // 2:\n",
    "                return i\n",
    "            else:\n",
    "                left_sum += i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pivotInteger(self, n: int) -> int:\n",
    "        num = (1+n)*n//2\n",
    "        for i in range(int(n//2),n+1):\n",
    "            if i*i/2 == num/2:\n",
    "                return i\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
